#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 1249. 移除无效的括号
// 给你一个由 '('、')' 和小写字母组成的字符串 s。
// 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

char* minRemoveToMakeValid(char* s) {
    size_t n = strlen(s);
    int* st = (int*)malloc(n * sizeof(int));    // 栈数组（整数数组模拟栈）
    int top = -1;   // 栈顶指针

    for(int i = 0; i < n; i++)
    {
        char ch = s[i];
        if(ch == '(') {
            top++;
            st[top] = i;
        }
        else if(ch == ')') {
            if(top != -1 && s[st[top]] == '(')  // 括号匹配，则出栈
                top--;
            else {
                top++;
                st[top] = i;
            }
        }
    } // for
    if(top == -1) return s; // 全部合法匹配
    // 将s中的无效括号用特殊符号'#'替换
    while(top != -1)
    {
        int i = st[top];    // 取出对应括号的序号i
        top--;
        s[i]='#';   // 替换为‘#’
    }
    // 把s中的 '#'一次性删除掉。整体前移法
    int i = 0, k = 0;
    while(i < n)
    {
        if(s[i] == '#')
            k++;
        else
            s[i-k] = s[i];  // 前移k个位置
        i++;
    }
    s[n-k] = '\0';
    return s;
}

int main()
{
    char s1[] = "lee(t(c)o)de)";
    printf("%s\n", minRemoveToMakeValid(s1));
    char s2[] = "a)b(c)d";
    printf("%s\n", minRemoveToMakeValid(s2));
    char s3[] = "))((";
    printf("%s\n", minRemoveToMakeValid(s3));
}